|
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an ''interval'' describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is ''compatible'' if no two intervals overlap. For example, the subset is compatible, as is the subset ; but neither nor are compatible subsets, because the corresponding intervals within each subset overlap. The ''interval scheduling maximization problem'' (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible. In an upgraded version of the problem, the intervals are partitioned into groups. A subset of intervals is ''compatible'' if no two intervals overlap, and moreover, no two intervals belong to the same group (i.e. the subset contains at most a single representative interval of each group). The ''group interval scheduling decision problem'' (GISDP) is to decide whether there exists a compatible set in which all groups are represented. The goal here is to execute a single representative task from each group. GISDPk is a restricted version of GISDP in which the number of intervals in each group is at most ''k''. The ''group interval scheduling maximization problem'' (GISMP) is to find a largest compatible set - a set of non-overlapping representatives of maximum size. The goal here is to execute a representative task from as many groups as possible. GISMPk is a restricted version of GISMP in which the number of intervals in each group is at most ''k''. This problem is often called JISPk, where J stands for Job. GISMP is the most general problem; the other two problems can be seen as special cases of it: * ISMP is the special case in which each task belongs to its own group (i.e. it is equal to GISMP1). * GISDP is the problem of deciding whether the maximum is exactly equal to the number of groups. ==Interval Scheduling Maximization== Several algorithms, that may look promising at first sight, actually do not find the optimal solution: * Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests. * Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interval scheduling」の詳細全文を読む スポンサード リンク
|